1. Field of the Invention
This invention relates to message forwarding, such as for example in a computer network, wireless network or intra or inter computer communication system.
2. Related Art
In interconnection networks, individual devices communicate with each other using messages, which are forwarded using a collection of routers (or switches) from a source device to a destination device. Messages include header information, which is used by the routers to determine how to treat those messages. For example, each router must decide which next-hop router to forward a message to so that the message ultimately reaches its proper destination.
There are at least three concerns each router must address when forwarding messages. First, routers perform a lookup for routing information in response to packet header information. Second, routers schedule the packet for sending in response to a result of the lookup operation. Third, routers forward the packet to an output queue for sending, and actually send the packet to a next hop location.
When performing the lookup operation, there are further concerns each router must address. First, routers need a rapid technique for determining how to treat the message in response to the destination address, including obtaining the “longest prefix match” for the header information. Second, routers need an efficient technique for recording all known destination prefixes addresses in memory and for updating that memory in response to changes in network topology. (While this operation does not take place for each lookup, the router still performs the operation from time to time.) Given the so-far rapid growth of the Internet, and the consequent rapid growth in both the number of possible destinations and the number of routing table entries, every step in this process requires accuracy and would benefit from speed.
The “longest prefix match” problem may be shown by an example. The destination address of a message directed to MIT maybe routed a first way; such messages may include a prefix that is broad and general. The destination address of a message directed to MIT's School of Architecture may be routed a second way, different from the first way and having priority over the first way. These distinctions and priorities are made by looking up the destination address in a table that associates a destination address with a next hop router and give preference to table entries that match the longest part of the destination address (this is referred to as “longest match”). Given the rapid expansion of the Internet, tables are relatively large and growing relatively rapidly. Hence, identifying the “longest match” has become increasingly difficult.
Longest prefix matching can be performed using a TCAM (ternary content addressable memory) or by using various different algorithms such as different trie structures. Both TCAMs and the various different algorithms have numerous drawbacks. TCAMS have relatively low memory density, perform at a limited clock speed, and so require multiple chips in order to achieve either relatively high speeds or relatively large table sizes.
Moreover, algorithms used in lookups have relatively large and elaborate data structures, thus requiring the use of off-chip memory (additional memory not integrated onto the same chip as the lookup circuits).
Known methods of matching destination addresses primarily use off-chip memory, in which the router (or switch) communicates with a memory device using a memory bus to retrieve information about routing messages. When off-chip memory is used, the memory can be either very dense but relatively slow, such as DRAM, or can be very fast but relatively less dense, such as off-chip SRAM. Using DRAM, the speed with which the router can reference memory (and the amount of bandwidth for memory access) limits the speed at which the router can process header information. The relative lesser density of off-chip SRAM means that the router uses multiple SRAM devices for the same amount of storage, and therefore devotes a relatively large number of its input/output pins to accessing memory (also limiting the ability to quickly access large amounts of memory). Either of these drawbacks severely limits the speed with which the router can operate.
Alternatively, routers may use “on-chip” memory, in which the router includes memory with routing information integrated onto the same monolithic semiconductor circuit with intelligent logic. However, on-chip SRAM memory sizes are relatively limited, so that relatively compact or small data structures are preferred. On-chip DRAM memory sizes are less limited, but on-chip DRAM is comparatively slow, and therefore less suitable for rapid lookup.
TCAMs have the advantage of not requiring large and elaborate data structures, because they are specially designed for the purpose of lookup, but they have relatively high power usage, low speed and low density. Avoiding specialized memories leads to using other data structures, which in the known art are relatively large and therefore use multiple memory devices—either multiple DRAM chips (to achieve larger storage), or multiple SRAM chips (to achieve higher speed).
Accordingly, it would be desirable to provide a technique for lookup of message header information that is not subject to drawbacks of the known art. This can be achieved using aspects of the invention in which a relatively compact and smaller data structure is used in combination with pipelined on-chip memory.